
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <title>11 容器 · C++导览 第二版 简体中文版</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="HonKit 5.1.1">
        <meta name="author" content="Windsting">
        
        
    
    <link rel="stylesheet" href="gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="gitbook/@dogatana/honkit-plugin-page-toc-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="gitbook/@dogatana/honkit-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="gitbook/gitbook-plugin-forkmegithub/plugin.css">
                
            
                
                <link rel="stylesheet" href="gitbook/@honkit/honkit-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="gitbook/gitbook-plugin-search/search.css">
                
            
                
                <link rel="stylesheet" href="gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
        <link rel="stylesheet" href="styles/website.css">
        
    
        
    
        
    
        
    
        
    
        
    

        
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="ch12.html" />
    
    
    <link rel="prev" href="ch10.html" />
    

    </head>
    <body>
        
<div class="book honkit-cloak">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    
    
        
        <li>
            <a href="https://github.com/windsting/a-tour-of-cpp-2nd-cn" target="_blank" class="custom-link">Github Link</a>
        </li>
    
    

    
    <li class="divider"></li>
    

    
        
        
    
        <li class="chapter " data-level="1.1" data-path="translation_note.html">
            
                <a href="translation_note.html">
            
                    
                    译者言
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="./">
            
                <a href="./">
            
                    
                    前言
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="ch01.html">
            
                <a href="ch01.html">
            
                    
                    1 基础知识
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="ch02.html">
            
                <a href="ch02.html">
            
                    
                    2 用户定义类型
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="ch03.html">
            
                <a href="ch03.html">
            
                    
                    3 模块化
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="ch04.html">
            
                <a href="ch04.html">
            
                    
                    4 类
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="ch05.html">
            
                <a href="ch05.html">
            
                    
                    5 基本操作
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="ch06.html">
            
                <a href="ch06.html">
            
                    
                    6 模板
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="ch07.html">
            
                <a href="ch07.html">
            
                    
                    7 概束和泛型编程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.10" data-path="ch08.html">
            
                <a href="ch08.html">
            
                    
                    8 标准库概览
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.11" data-path="ch09.html">
            
                <a href="ch09.html">
            
                    
                    9 字符串和正则表达式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.12" data-path="ch10.html">
            
                <a href="ch10.html">
            
                    
                    10 输入输出
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="1.13" data-path="ch11.html">
            
                <a href="ch11.html">
            
                    
                    11 容器
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.14" data-path="ch12.html">
            
                <a href="ch12.html">
            
                    
                    12 算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.15" data-path="ch13.html">
            
                <a href="ch13.html">
            
                    
                    13 实用功能
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.16" data-path="ch14.html">
            
                <a href="ch14.html">
            
                    
                    14 数值
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.17" data-path="ch15.html">
            
                <a href="ch15.html">
            
                    
                    15 并发
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.18" data-path="ch16.html">
            
                <a href="ch16.html">
            
                    
                    16 历史及兼容性
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.19" data-path="idx.html">
            
                <a href="idx.html">
            
                    
                    索引
            
                </a>
            

            
        </li>
    

    

    <li class="divider"></li>

    <li>
        <a href="https://github.com/honkit/honkit" target="blank" class="gitbook-link">
            本书使用 HonKit 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href="." >11 容器</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                

    
        
                                <p><a class="en-page-number" id="137"></a></p>
<div class="chapter-number"><p class="chapter-number">11</p></div>

<h1 id="container">容器 </h1>
<blockquote>
<p>它新颖。</p>
<p>它卓越。</p>
<p>它简洁。</p>
<p>它必将成功！</p>
<p><span title="这句话的原文出自“The Letters of Lord Nelson to Lady Hamilton, Vol II.”书中的“LETTER LX.”，该书可在网址 https://www.gutenberg.org/ebooks/15437 查阅，未发现中文译本。" 。>—— 霍雷肖·纳尔逊</span><sup><a href="#fn_1" id="reffn_1">1</a></sup></p>
</blockquote>
<h2 id="11.1">11.1 导言 </h2>
<p>大多数计算都要涉及创建值的集合，并且还要操作这些集合。
把一些字符读进一个<code>string</code>再打印出这个<code>string</code>就是简单的例子。
如果某个类的主要用途是装载一些对象，它通常被称为<em>容器（container）</em>。
在构建程序过程中，有个至关重要的任务：
为给定任务提供合适的容器，并使用便利的基础操作为它们提供支持。</p>
<p>为阐明标准库容器，请考虑一个程序用于保存名字和电话号码。
对于不同背景的人，这个程序会以不同的方法归类到“简单且明了”的分类中。
§10.5 中的 <code>Entry</code>类可用于保存一个简单的电话簿条目。
此处，我们有意忽略了现实世界的许多复杂性，
例如“很多电话号码无法以32位<code>int</code>表示”的这个情况。</p>
<p><a class="en-page-number" id="138"></a></p>
<h2 id="11.2">11.2 <code>vector</code> </h2>
<p>最有用的标准库容器是<code>vector</code>。<code>vector</code>是给定类型元素的一个序列。
这些元素在内存中连续存储。
<code>vector</code>典型的实现（§4.2.2，§5.2）会包含一些指针，指向首元素、
最后一个元素后的位置、已分配空间后的位置（§12.1）（或以指针加偏移表示的等价信息）：</p>
<p><img src="img/ch11_01.png" alt="vector-layout"></p>
<p>此外，它还会包含一个内存分配器（此处的<code>alloc</code>），
<code>vector</code>可以用它为元素申请内存。
默认的内存分配器使用<code>new</code>和<code>delete</code>对内存进行申请和释放（§13.6）。</p>
<p>可以用一组元素类型的值对<code>vector</code>进行初始化：</p>
<pre><code class="lang-cpp">vector&lt;Entry&gt; phone_book = {
    {<span class="hljs-string">&quot;David Hume&quot;</span>,<span class="hljs-number">123456</span>},
    {<span class="hljs-string">&quot;Karl Popper&quot;</span>,<span class="hljs-number">234567</span>},
    {<span class="hljs-string">&quot;Bertrand Arthur William Russell&quot;</span>,<span class="hljs-number">345678</span>}
};
</code></pre>
<p>元素可以通过下标进行访问。假设已经为<code>Entry</code>定义了<code>&lt;&lt;</code>，可以写：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">print_book</span><span class="hljs-params">(<span class="hljs-type">const</span> vector&lt;Entry&gt;&amp; book)</span>
</span>{
    <span class="hljs-keyword">for</span> (<span class="hljs-type">int</span> i = <span class="hljs-number">0</span>; i!=book.<span class="hljs-built_in">size</span>(); ++i)
        cout &lt;&lt; book[i] &lt;&lt; <span class="hljs-string">&apos;\n&apos;</span>;
}
</code></pre>
<p>按惯例，下标自<code>0</code>开始，因此<code>book[0]</code>保存着<code>David Hume</code>的条目。
<code>vector</code>的成员函数<code>size()</code>给出元素的数量。</p>
<p><code>vector</code>的元素构成一个区间，因此可以应用区间-<code>for</code>循环（§1.7）：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">print_book</span><span class="hljs-params">(<span class="hljs-type">const</span> vector&lt;Entry&gt;&amp; book)</span>
</span>{
    <span class="hljs-keyword">for</span> (<span class="hljs-type">const</span> <span class="hljs-keyword">auto</span>&amp; x : book)  <span class="hljs-comment">// 关于 &quot;auto&quot;， 见 §1.4</span>
        cout &lt;&lt; x &lt;&lt; <span class="hljs-string">&apos;\n&apos;</span>;
}
</code></pre>
<p>定义一个<code>vector</code>的时候，会给它一个初始容量（元素的初始数量）：</p>
<pre><code class="lang-cpp">vector&lt;<span class="hljs-type">int</span>&gt; v1 = {<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>};  <span class="hljs-comment">// 容量为 4</span>
vector&lt;string&gt; v2;              <span class="hljs-comment">// 容量为 0</span>
<span class="hljs-function">vector&lt;Shape*&gt; <span class="hljs-title">v3</span><span class="hljs-params">(<span class="hljs-number">23</span>)</span></span>;          <span class="hljs-comment">// 容量为 23；初始元素值：nullptr</span>
<span class="hljs-function">vector&lt;<span class="hljs-type">double</span>&gt; <span class="hljs-title">v4</span><span class="hljs-params">(<span class="hljs-number">32</span>,<span class="hljs-number">9.9</span>)</span></span>;      <span class="hljs-comment">// 容量为 32；初始元素值：9.9</span>
</code></pre>
<p><a class="en-page-number" id="139"></a></p>
<p>显式的容量由一对普通的小括号包围，例如<code>(23)</code>，默认情况下，
这些元素被初始化为元素类型的默认值（即：指针为<code>nullptr</code>，而数值为<code>0</code>）。
如果你不想使用默认值，可以通过第二个参数指定一个值
（即：<code>9.9</code>之于<code>v4</code>的<code>32</code>个元素那样）。</p>
<p>初始容量可变的。
<code>vector</code>最有用的一个操作是<code>push_back()</code>，
它在<code>vector</code>末尾添加一个新元素，并将其容量加一。
例如，假设我们为<code>Entry</code>定义了<code>&gt;&gt;</code>，就可以这样写：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">input</span><span class="hljs-params">()</span>
</span>{
    <span class="hljs-keyword">for</span> (Entry e; cin&gt;&gt;e; )
        phone_book.<span class="hljs-built_in">push_back</span>(e);
}
</code></pre>
<p>这段代码从标准输入读取<code>Entry</code>放到<code>phone_book</code>中，
遇到输入结束（end-of-input）（即 到达文件末尾）或读取操作遭遇格式错误都会停止。</p>
<p>标准库中<code>vector</code>的具体实现确保了反复通过<code>push_back()</code>增长这个操作的效率。
为演示其方法，请考虑这个精致的简化版<code>Vector</code>（第4章和第6章），其结构如上图所示：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> T&gt;
<span class="hljs-keyword">class</span> <span class="hljs-title class_">Vector</span> {
    T* elem;    <span class="hljs-comment">// 指向首个元素的指针</span>
    T* space;   <span class="hljs-comment">// 指向首个未使用（且未初始化）的空位的指针</span>
    T* last;    <span class="hljs-comment">// 指向最后一个空位的指针</span>
<span class="hljs-keyword">public</span>:
    <span class="hljs-comment">// ...</span>
    <span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">size</span><span class="hljs-params">()</span></span>;                 <span class="hljs-comment">// 元素数量 (space-elem)</span>
    <span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">capacity</span><span class="hljs-params">()</span></span>;             <span class="hljs-comment">// 可容纳元素的数量 (last-elem)</span>
    <span class="hljs-comment">// ...</span>
    <span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">reserve</span><span class="hljs-params">(<span class="hljs-type">int</span> newsz)</span></span>;    <span class="hljs-comment">// 增加 capacity() 到 newsz</span>
    <span class="hljs-comment">// ...</span>
    <span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">push_back</span><span class="hljs-params">(<span class="hljs-type">const</span> T&amp; t)</span></span>; <span class="hljs-comment">// 把 t 复制进 Vector</span>
    <span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">push_back</span><span class="hljs-params">(T&amp;&amp; t)</span></span>;      <span class="hljs-comment">// 把 t 移动进 Vector</span>
};
</code></pre>
<p>标准库的<code>vector</code>具有成员<code>capacity()</code>、<code>reverse()</code>和<code>push_back()</code>。
<code>reserve()</code>供<code>vector</code>的用户和其它成员函数使用，用途是为将来的元素预留空间。
它可能不得不分配新的内存，此时，它会将当前的元素移至新分配的内存里。</p>
<p>有了<code>capacity()</code>和<code>reverse()</code>，实现<code>push_back()</code>就轻而易举了：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> T&gt;
<span class="hljs-type">void</span> Vector&lt;T&gt;::<span class="hljs-built_in">push_back</span>(<span class="hljs-type">const</span> T&amp; t)
{
    <span class="hljs-keyword">if</span> (<span class="hljs-built_in">capacity</span>()&lt;<span class="hljs-built_in">size</span>()+<span class="hljs-number">1</span>)            <span class="hljs-comment">// 确保有空间保存 t</span>
        <span class="hljs-built_in">reserve</span>(<span class="hljs-built_in">size</span>()==<span class="hljs-number">0</span>?<span class="hljs-number">8</span>:<span class="hljs-number">2</span>*<span class="hljs-built_in">size</span>());  <span class="hljs-comment">// 把容量翻倍</span>
    <span class="hljs-keyword">new</span>(space) T{t};                    <span class="hljs-comment">// 将 *space 初始化为 t</span>
    ++space;
}
</code></pre>
<p><a class="en-page-number" id="140"></a></p>
<p>如此一来，分配内存和移动元素位置就不至于很频繁。
我曾经试图利用<code>reserve()</code>提高性能，但结果是白费力气：
总的来说，<code>vector</code>的方法优于我的臆测，因此，我目前只会在用指针指向其元素时，
才显式调用<code>reserve()</code>，以避免元素移动位置（而导致指针空悬——译者）。</p>
<p><code>vector</code>可以在赋值和初始化的时候被复制。例如：</p>
<pre><code class="lang-cpp">vector&lt;Entry&gt; book2 = phone_book;
</code></pre>
<p><code>vector</code>的复制和移动经由构造函数和赋值运算符实现，详情请见 §5.2。
赋值<code>vector</code>涉及复制其元素。
因此，在<code>book2</code>初始化后，<code>book2</code>和<code>phone_book</code>为每个<code>Entry</code>分别保存副本。
当一个<code>vector</code>存有大量元素，这种看似人畜无害的赋值和初始化就会代价高昂。
在不该执行复制操作的地方，应该使用引用或指针（§1.7），或者移动操作（§5.2.2）。</p>
<p>标准库的<code>vector</code>非常灵活而高效。请把它作为你默认的容器；
就是说，除非你有足够的理由使用其它容器，否则就应该用它。
如果你出于“效率”考量方面的担忧而打算弃用<code>vector</code>，请测试一下效率。
在容器使用的性能方面，我们的直觉往往漏洞百出。</p>
<h3 id="11.2.1">11.2.1 元素 </h3>
<p>与所有标准库容器相似，<code>vector</code>是个某种类型<code>T</code>元素的容器，
简言之是个<code>vector&lt;T&gt;</code>。
任何类型都可以成为元素类型：内建的数值类型（例如<code>char</code>、<code>int</code>和<code>double</code>），
用户定义类型（例如<code>string</code>、<code>Entry</code>、<code>list&lt;T&gt;</code>及<code>Matrix&lt;double,2&gt;</code>），
以及指针（例如<code>const char*</code>、<code>Shape*</code>和<code>double*</code>）。
当你插入一个新元素，它的值会被复制进入容器。
例如，当你把一个值为<code>7</code>的整数放进元素，所产生元素的值为<code>7</code>。
该元素不是指向某个装载着<code>7</code>的对象的引用或指针。
这样做可令容器优雅、紧凑且访问迅速。
对于在意内存消耗以及运行时性能的用户，这至关重要。</p>
<p>如果你有一个类体系（§4.5），该体系依赖于<code>virtual</code>函数以实现多态行为，
别直接在容器里保存对象。用指针（或者智能指针；§13.2.1）取代它。例如：</p>
<pre><code class="lang-cpp">vector&lt;Shape&gt; vs;               <span class="hljs-comment">// 别这么做——没有空间容纳 Circle 或 Smiley</span>
vector&lt;Shape*&gt; vps;             <span class="hljs-comment">// 好一些，参看 §4.5.3</span>
vector&lt;unique_ptr&lt;Shape&gt;&gt; vups; <span class="hljs-comment">// OK</span>
</code></pre>
<h3 id="11.2.2">11.2.2 越界检查 </h3>
<p>标准库<code>vector</code>不保证进行越界检查。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">silly</span><span class="hljs-params">(vector&lt;Entry&gt;&amp; book)</span>
</span>{
    <span class="hljs-type">int</span> i = book[book.<span class="hljs-built_in">size</span>()].number; <span class="hljs-comment">// book.size() 越界了</span>
    <span class="hljs-comment">// ...</span>
}
</code></pre>
<p><a class="en-page-number" id="141"></a></p>
<p>那条初始化语句很可能给<code>i</code>一个不确定的值，而不是报错。
这可不合时宜，而且越界访问（out-of-range）是个常见的问题。
因此，我通常使用一个带有越界检查的<code>vector</code>修改版：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">template</span>&lt;<span class="hljs-keyword">typename</span> T&gt;
<span class="hljs-keyword">class</span> <span class="hljs-title class_">Vec</span> : <span class="hljs-keyword">public</span> std::vector&lt;T&gt; {
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">using</span> vector&lt;T&gt;::vector;            <span class="hljs-comment">// （以名称Vec）使用vector的构造函数</span>

    T&amp; <span class="hljs-keyword">operator</span>[](<span class="hljs-type">int</span> i)                <span class="hljs-comment">// 越界检查</span>
        { <span class="hljs-keyword">return</span> vector&lt;T&gt;::<span class="hljs-built_in">at</span>(i); }

    <span class="hljs-type">const</span> T&amp; <span class="hljs-keyword">operator</span>[](<span class="hljs-type">int</span> i) <span class="hljs-type">const</span>    <span class="hljs-comment">// const 对象的越界检查； §4.2.1</span>
        { <span class="hljs-keyword">return</span> vector&lt;T&gt;::<span class="hljs-built_in">at</span>(i); }
};
</code></pre>
<p>除了为越界检查重定义过的取下标操作以外，<code>Vec</code>从<code>vector</code>继承了所有内容。
<code>at()</code>是个<code>vector</code>的取下标操作，如果其参数越界了，
它将抛出<code>out_of_range</code>类型的异常（§3.5.1）。</p>
<p>对于<code>Vec</code>来说，越界访问将抛出异常供用户捕获。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">checked</span><span class="hljs-params">(Vec&lt;Entry&gt;&amp; book)</span>
</span>{
    <span class="hljs-keyword">try</span> {
        book[book.<span class="hljs-built_in">size</span>()] = {<span class="hljs-string">&quot;Joe&quot;</span>,<span class="hljs-number">999999</span>}; <span class="hljs-comment">// 将会抛出异常</span>
        <span class="hljs-comment">// ...</span>
    }
    <span class="hljs-built_in">catch</span> (out_of_range&amp;) {
        cerr &lt;&lt; <span class="hljs-string">&quot;range error\n&quot;</span>;
    }
}
</code></pre>
<p>这将会抛出异常，然后被捕获（§3.5.1）。
如果用户不捕获某个异常，程序会以良好定义的方式终止，
而不是继续运行或导致未定义的行为。
有个方法会尽可能避免未捕获异常导致的慌乱，
就是用<code>try</code>-块作为<code>main()</code>的函数体。
例如：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>
<span class="hljs-keyword">try</span> </span>{
    <span class="hljs-comment">// 你的代码</span>
}
<span class="hljs-built_in">catch</span> (out_of_range&amp;) {
    cerr &lt;&lt; <span class="hljs-string">&quot;range error\n&quot;</span>;
}
<span class="hljs-built_in">catch</span> (...) {
    cerr &lt;&lt; <span class="hljs-string">&quot;unknown exception thrown\n&quot;</span>;
}
</code></pre>
<p>这提供了缺省的的异常处理，对于漏掉的异常，
会有一条错误信息输出到标准错误诊断流<code>cerr</code>（§10.2）。</p>
<p><a class="en-page-number" id="142"></a></p>
<p>为什么标准不确保越界检查呢？
许多追求性能的应用程序使用<code>vector</code>，而对所有的取下标操作意味着10%的性能损失。
显而易见，该性能损失对于不同的硬件、优化器和执行的取下标操作而有所不同。
然而，经验显示此代价会导致人们转而采用安全性奇差的内建数组。
尽管对此代价的些许担忧会导致弃用。
<code>vector</code>在debug时仍易于进行越界检查，
而且还可以在未检查的默认版本上构建提供检查的版本。
某些编译器提供了带有越界检查的<code>vector</code>版本（即：使用编译器选项），
以解除你定义<code>Vec</code>（或等价物）的烦恼。</p>
<p>区间-<code>for</code>借助迭代器在[<code>bdgin()</code>:<code>end()</code>)区间访问元素以避免越界错误。
只要其迭代器参数有效，标准库中的算法以同样的机制确保越界错误不会发生。</p>
<p>如果你可以在代码中直接使用<code>vector::at()</code>，就无需使用我那个<code>Vec</code>变通方案。
另外，某些标准库具备带有越界检查的<code>vector</code>实现，提供了比<code>Vec</code>更完善的检查。</p>
<h2 id="11.3">11.3 <code>list</code> </h2>
<p>标准库提供了一个名为<code>list</code>的双向链表：</p>
<p><img src="img/ch11_02.png" alt="list-layout"></p>
<p>对于某些序列，需要在插入和删除元素时避免移动其它元素，此时我们为其应用<code>list</code>。
对于电话薄，插入和删除是常规操作，因此用<code>list</code>表示电话薄就很适宜。例如：</p>
<pre><code class="lang-cpp">list&lt;Entry&gt; phone_book = {
    {<span class="hljs-string">&quot;David Hume&quot;</span>,<span class="hljs-number">123456</span>},
    {<span class="hljs-string">&quot;Karl Popper&quot;</span>,<span class="hljs-number">234567</span>},
    {<span class="hljs-string">&quot;Bertrand Arthur William Russell&quot;</span>,<span class="hljs-number">345678</span>}
};
</code></pre>
<p>在使用链表时，通常不会像使用vector那样以取下标的方式访问元素。
相反，会为了找到某个给定值而对链表进行查找操作。
为此，我们要借助第12章提及的“<code>list</code>是个序列”这一优势：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">get_number</span><span class="hljs-params">(<span class="hljs-type">const</span> string&amp; s)</span>
</span>{
    <span class="hljs-keyword">for</span> (<span class="hljs-type">const</span> <span class="hljs-keyword">auto</span>&amp; x : phone_book)
        <span class="hljs-keyword">if</span> (x.name==s)
            <span class="hljs-keyword">return</span> x.number;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;   <span class="hljs-comment">// 用 0 表示“号码未发现”</span>
}
</code></pre>
<p><a class="en-page-number" id="143"></a></p>
<p>对<code>s</code>的查找自链表的头部开始一路向后执行，直至找到<code>s</code>或者抵达<code>phone_book</code>的尾部。</p>
<p>有时候，我们需要确定<code>list</code>中的某个元素。
例如，可能需要删除某个元素或在其前面插入一个元素。
此操作需要使用<em>迭代器（iterator）</em>：<code>list</code>的迭代器确定<code>list</code>中的某个元素，
还可以用于遍历（iterate）该<code>list</code>（并由此得名）。
所有的标准库容器都提供<code>begin()</code>和<code>end()</code>函数，
它们分别返回指向首元素和尾元素之后一个位置
（one-beyond-the-end）的迭代器（第12章）。
使用迭代器可以——略失优雅地——这样写<code>get_number()</code>：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">get_number</span><span class="hljs-params">(<span class="hljs-type">const</span> string&amp; s)</span>
</span>{
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">auto</span> p = phone_book.<span class="hljs-built_in">begin</span>(); p!=phone_book.<span class="hljs-built_in">end</span>(); ++p)
        <span class="hljs-keyword">if</span> (p-&gt;name==s)
            <span class="hljs-keyword">return</span> p-&gt;number;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;   <span class="hljs-comment">// 用 0 表示“号码未发现”</span>
}
</code></pre>
<p>实际上，编译器大致就是这样实现了更简洁且更不易出错的区间-<code>for</code>。
给定一个迭代器<code>p</code>，<code>*p</code>就是它指向的元素，<code>++p</code>自增<code>p</code>，使之指向下一个元素，
当<code>p</code>指向一个具有成员<code>m</code>的类，<code>p-&gt;m</code>等价于<code>(*p).m</code>。</p>
<p>向<code>list</code>添加和从中删除元素都很简单：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">void</span> <span class="hljs-title">f</span><span class="hljs-params">(<span class="hljs-type">const</span> Entry&amp; ee, list&lt;Entry&gt;::iterator p, list&lt;Entry&gt;::iterator q)</span> </span>{
    phone_book.<span class="hljs-built_in">insert</span>(p,ee);    <span class="hljs-comment">// 在 p 指向的元素前插入 ee</span>
    phone_book.<span class="hljs-built_in">erase</span>(q);        <span class="hljs-comment">// 移除 q 指向的元素</span>
}
</code></pre>
<p>对于<code>list</code>，<code>insert(p,elem)</code>在<code>p</code>指向的元素前插入<code>elem</code>的一个副本作为元素。
此处，<code>p</code>可能是一个指向<code>list</code>尾元素后一个位置的迭代器。
反之，<code>erase(p)</code>移除<code>p</code>指向的元素并销毁它。</p>
<p>这些<code>list</code>的例子都可以使用<code>vector</code>并以相同的方式去写，
并且（惊人的是，除非你理解机器架构）在一个小<code>vector</code>上的性能优于小<code>list</code>。
如果我们只需要一个元素的序列，那就用<code>vector</code>。
<code>vector</code>在遍历（即<code>find()</code>和<code>count()</code>）及排序和查找（即<code>sort()</code>、
<code>equal_range()</code>；§12.6，§13.4.3）方面的性能更好。</p>
<p>标准库还提供了一个名为<code>forward_list</code>的单链表：</p>
<p><img src="img/ch11_03.png" alt="forward_list-layout"></p>
<p><code>forward_list</code>跟<code>list</code>的区别是它仅允许前向遍历。其目的是节约存储空间。
它无需在每个节点上都保存前一个元素的指针，
并且空<code>forward_list</code>只占用一个指针的空间。
<code>forward_list</code>甚至不保存其元素数量，如果你需要知道元素数量，就得数一遍。
如果你无法承担计数元素数量的开销，可能就不该用<code>forward_list</code>。</p>
<p><a class="en-page-number" id="144"></a></p>
<h2 id="11.4">11.4 <code>map</code> </h2>
<p>通过写代码，在一个<em>(name,number)</em>对的列表里面查找某个name相当烦冗。
另外，线性查找对于短列表以外的情况都效率低下。
标准库还提供一个名为<code>map</code>的平衡二叉树（通常是红黑树）：</p>
<p><img src="img/ch11_04.png" alt="map-layout"></p>
<p>在其它语境中，<code>map</code>也被称为关联数组或字典。它以平衡二叉树的方式实现。</p>
<p>标准库<code>map</code>是一个承载 值对 的容器，针对查找进行了优化。
可以跟<code>list</code>和<code>vector</code>以相同的方式进行初始化（§11.2，§11.3）：</p>
<pre><code class="lang-cpp">map&lt;string,<span class="hljs-type">int</span>&gt; phone_book {
    {<span class="hljs-string">&quot;David Hume&quot;</span>,<span class="hljs-number">123456</span>},
    {<span class="hljs-string">&quot;Karl Popper&quot;</span>,<span class="hljs-number">234567</span>},
    {<span class="hljs-string">&quot;Bertrand Arthur William Russell&quot;</span>,<span class="hljs-number">345678</span>}
};
</code></pre>
<p>当使用其中第一个类型（被称为<em>键（key）</em>）的值去索引时，<code>map</code>返回对应的第二个类型
（被称为 <em>值（value）</em> 或 <em>映射类型（mapped type）</em>）的值。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">get_number</span><span class="hljs-params">(<span class="hljs-type">const</span> string&amp; s)</span>
</span>{
    <span class="hljs-keyword">return</span> phone_book[s];
}
</code></pre>
<p>换句话说，对<code>map</code>取下标基本上就是我们称之为<code>get_number()</code>的查找操作。
如果没找到<code>key</code>，那么它就跟<code>value</code>的默认值一起被插入<code>map</code>。
整数的默认值是<code>0</code>；恰恰是我选取的用于表示无效电话号码的值。</p>
<p>如果要避免将无效号码插入电话薄，可以用<code>find()</code>和<code>insert()</code>替代<code>[]</code>。</p>
<h2 id="11.5">11.5 <code>unordered_map</code> </h2>
<p><code>map</code>的查找开销是<code>O(log(n))</code>，其中<code>n</code>是<code>map</code>的元素数量。这已经相当好了。
比方说对于具有 1,000,000 个元素的<code>map</code>，
只需要大约20次比对和转向即可找到某个元素。</p>
<p><a class="en-page-number" id="145"></a></p>
<p>不过，在很多情况下，使用哈希（hash）查找而非<code>&lt;</code>这样的排序比对函数，还能更进一步。
标准库的哈希容器被称为“无序（unordered）”，是因为他们不需要一个排序比对函数：</p>
<p><img src="img/ch11_05.png" alt="unordered_map-layout"></p>
<p>例如，可以用<code>&lt;unordered_map&gt;</code>中的<code>unordered_map</code>实现电话薄：</p>
<pre><code class="lang-cpp">unordered_map&lt;string,<span class="hljs-type">int</span>&gt; phone_book {
    {<span class="hljs-string">&quot;David Hume&quot;</span>,<span class="hljs-number">123456</span>},
    {<span class="hljs-string">&quot;Karl Popper&quot;</span>,<span class="hljs-number">234567</span>},
    {<span class="hljs-string">&quot;Bertrand Arthur William Russell&quot;</span>,<span class="hljs-number">345678</span>}
};
</code></pre>
<p>就像使用<code>map</code>那样，可以对<code>unordered_map</code>取下标：</p>
<pre><code class="lang-cpp"><span class="hljs-function"><span class="hljs-type">int</span> <span class="hljs-title">get_number</span><span class="hljs-params">(<span class="hljs-type">const</span> string&amp; s)</span>
</span>{
    <span class="hljs-keyword">return</span> phone_book[s];
}
</code></pre>
<p>标准库为<code>string</code>和其它内建及标准库类型提供了缺省的哈希函数。
如果有必要，你可以提供你自己的版本（§5.4.6）。</p>
<p>对于“定制的”哈希函数，最常见的需求可能就来自于我们要为自己的类型创建无序容器。
哈希函数通常以函数对象（§6.3.2）的形式提供。例如：</p>
<pre><code class="lang-cpp"><span class="hljs-keyword">struct</span> <span class="hljs-title class_">Record</span> {
    string name;
    <span class="hljs-type">int</span> product_code;
    <span class="hljs-comment">// ...</span>
};

<span class="hljs-keyword">struct</span> <span class="hljs-title class_">Rhash</span> {  <span class="hljs-comment">// 针对 Record 的哈希函数</span>
    <span class="hljs-function"><span class="hljs-type">size_t</span> <span class="hljs-title">operator</span><span class="hljs-params">()</span><span class="hljs-params">(<span class="hljs-type">const</span> Record&amp; r)</span> <span class="hljs-type">const</span>
    </span>{
        <span class="hljs-keyword">return</span> <span class="hljs-built_in">hash</span>&lt;string&gt;()(r.name) ˆ <span class="hljs-built_in">hash</span>&lt;<span class="hljs-type">int</span>&gt;()(r.product_code);
    }
};

unordered_set&lt;Record,Rhash&gt; my_set; <span class="hljs-comment">// Record类型的set，使用Rhash进行查找</span>
</code></pre>
<p>良好哈希函数的设计是一门艺术，有时候需要对使用它的数据有一定的了解。
把现有的哈希函数用异或（<code>^</code>）进行组合从而创建一个新哈希函数很简单，通常也很高效。</p>
<p>如果定义成标准库<code>hash</code>的一个特化，就不必显式传递<code>hash</code>操作了：</p>
<p><a class="en-page-number" id="146"></a></p>
<pre><code class="lang-cpp"><span class="hljs-keyword">namespace</span> std { <span class="hljs-comment">// 给 Record 弄个哈希函数</span>
    <span class="hljs-keyword">template</span>&lt;&gt; <span class="hljs-keyword">struct</span> <span class="hljs-title class_">hash</span>&lt;Record&gt; {
        <span class="hljs-keyword">using</span> argument_type = Record;
        <span class="hljs-keyword">using</span> result_type = std::<span class="hljs-type">size_t</span>;

        <span class="hljs-function"><span class="hljs-type">size_t</span> <span class="hljs-title">operator</span><span class="hljs-params">()</span><span class="hljs-params">(<span class="hljs-type">const</span> Record&amp; r)</span> <span class="hljs-type">const</span>
        </span>{
            <span class="hljs-keyword">return</span> <span class="hljs-built_in">hash</span>&lt;string&gt;()(r.name) ˆ <span class="hljs-built_in">hash</span>&lt;<span class="hljs-type">int</span>&gt;()(r.product_code);
        }
    };
}
</code></pre>
<p>请注意<code>map</code>和<code>unordered_map</code>之间的差异：</p>
<ul>
<li><code>map</code>需要一个排序比对函数（默认情况下是<code>&lt;</code>）并产生一个有序的序列</li>
<li><code>unordered_map</code>需要一个相等性判定函数（默认情况下是<code>==</code>）；
  它不会维护元素间的顺序。</li>
</ul>
<p>给定一个好的哈希函数，对于大容量的容器，<code>unordered_map</code>会比<code>map</code>快很多。
不过，对于糟糕的哈希函数，<code>unordered_map</code>的最差情况又比<code>map</code>差很多。</p>
<h2 id="11.6">11.6 容器概览 </h2>
<p>标准库提供了某些最常规且有用的容器类型，以便程序员从中挑选最适合的去构建应用：</p>
<table style="width:80%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>标准容器概要</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:30%"><code>vector&lt;T&gt;</code></td>
            <td>长度可变的数组（§11.2）</td>
        </tr>
        <tr>
            <td><code>list&lt;T&gt;</code></td>
            <td>双向链表（§11.3）</td>
        </tr>
        <tr>
            <td><code>forward_list&lt;T&gt;</code></td>
            <td>单链表</td>
        </tr>
        <tr>
            <td><code>deque&lt;T&gt;</code></td>
            <td>双向队列</td>
        </tr>
        <tr>
            <td><code>set&lt;T&gt;</code></td>
            <td>集合（有key无value的<code>map</code>）</td>
        </tr>
        <tr>
            <td><code>multiset&lt;T&gt;</code></td>
            <td>同一个值可以存在多份的集合</td>
        </tr>
        <tr>
            <td><code>map&lt;K,V&gt;</code></td>
            <td>关联数组（§11.4）</td>
        </tr>
        <tr>
            <td><code>multimap&lt;K,V&gt;</code></td>
            <td>同一个key可以存在多份的map</td>
        </tr>
        <tr>
            <td><code>unordered_map&lt;K,V&gt;</code></td>
            <td>使用哈希查找的map（§11.5）</td>
        </tr>
        <tr>
            <td><code>unordered_multimap&lt;K,V&gt;</code></td>
            <td>使用哈希查找的multimap</td>
        </tr>
        <tr>
            <td><code>unordered_set&lt;T&gt;</code></td>
            <td>使用哈希查找的set</td>
        </tr>
        <tr>
            <td><code>unordered_multiset&lt;T&gt;</code></td>
            <td>使用哈希查找的multiset</td>
        </tr>
    </tbody>
</table>

<p>无序容器为通过key（通常是字符串）查找而优化；换句话说它们是用哈希表实现的。</p>
<p>这些容器定义在命名空间<code>std</code>中，
并放置在<code>vector</code>、<code>list</code>、<code>map</code>等头文件（§8.3）里。
另外，标准库还提供容器适配器<code>queue&lt;T&gt;</code>、<code>stack&lt;T&gt;</code>、<code>priority_queue&lt;T&gt;</code>。
如果你需要，请查找它们。
标准库还提供更多特化的类容器（container-like）类型，</p>
<p><a class="en-page-number" id="147"></a></p>
<p>例如<code>array&lt;T,N&gt;</code>（§13.4.1）和<code>bitset&lt;N&gt;</code>（§13.4.2）。</p>
<p>从书写形式的角度看，标准容器及其基本操作被设计得相互形似。
而且，对于不同容器而言操作的语意是等价的。
可应用于每种容器的，有意义且实现高效的基本操作包括：</p>
<table style="width:90%;margin-left:auto;margin-right:auto;">
    <tbody>
        <tr>
            <th colspan="2" style="text-align: center">
                <strong>标准容器操作（部分）</strong><br>
            </th>
        </tr>
        <tr>
            <td style="width:35%"><code>value_type</code></td>
            <td>
                元素的类型
            </td>
        </tr>
        <tr><td colspan="2"></td></tr>
        <tr>
            <td><code>p=c.begin()</code></td>
            <td>
                <code>p</code>指向<code>c</code>的首个元素；
                还有返回<code>const</code>迭代器的<code>cbegin()</code>
            </td>
        </tr>
        <tr>
            <td><code>p=c.end()</code></td>
            <td>
                <code>p</code>指向<code>c</code>的尾元素后的位置；
                还有返回<code>const</code>迭代器的<code>cend()</code>
            </td>
        </tr>
        <tr>
            <td><code>k=c.size()</code></td>
            <td>
                <code>k</code>是<code>c</code>中元素的数量
            </td>
        </tr>
        <tr>
            <td><code>c.empty()</code></td>
            <td><code>c</code>是否为空？</td>
        </tr>
        <tr>
            <td><code>k=c.capacity()</code></td>
            <td>
                <code>k</code>是<code>c</code>无需申请新内存的情况下所能承载的元素数量
            </td>
        </tr>
        <tr>
            <td><code>c.reserve(k)</code></td>
            <td>把capacity变成<code>k</code></td>
        </tr>
        <tr>
            <td><code>c.resize(k)</code></td>
            <td>把元素数量改成<code>k</code>；新增元素的值为<code>value_type{}</code></td>
        </tr>
        <tr>
            <td><code>c[k]</code></td>
            <td><code>c</code>的第<code>k</code>个元素；不做越界检查</td>
        </tr>
        <tr>
            <td><code>c.at(k)</code></td>
            <td>
                <code>c</code>的第<code>k</code>个元素；若越界则抛出<code>out_of_range</code>
            </td>
        </tr>
        <tr>
            <td><code>c.push_back(x)</code></td>
            <td>
                把<code>x</code>添加到<code>c</code>末尾；并把<code>c</code>的size加一
            </td>
        </tr>
        <tr>
            <td><code>c.emplace_back(a)</code></td>
            <td>
                把<code>value_type{a}</code>添加到<code>c</code>末尾；并把<code>c</code>的size加一
            </td>
        </tr>
        <tr>
            <td><code>q=c.insert(p,x)</code></td>
            <td>
                在<code>c</code>中把<code>x</code>添加到<code>p</code>前
            </td>
        </tr>
        <tr>
            <td><code>q=c.erase(p)</code></td>
            <td>
                从<code>c</code>中删除<code>p</code>
            </td>
        </tr>
        <tr><td colspan="2"></td></tr>
        <tr>
            <td><code>c=c2</code></td>
            <td>赋值</td>
        </tr>
        <tr>
            <td><code>b=(c==c2)</code>，以及<code>!=</code></td>
            <td>
                <code>c</code>和<code>c2</code>中的元素是否全相等；如果相等<code>b==true</code>
            </td>
        </tr>
        <tr>
            <td><code>x=(c&lt;c2)</code>，
            以及<code>&lt;=</code>、<code>&gt;</code>、<code>&gt;=</code></td>
            <td>
                <code>c</code>和<code>c2</code>的字典序：
                若小于则<code>x&lt;0</code>，
                若相等则<code>x==0</code>，
                若大于则<code>0&lt;x</code>
            </td>
        </tr>
    </tbody>
</table>

<p>这种符号跟语意的一致性使得程序员能够创造新的容器类型，并能在用法上与标准容器类似。
提供越界检查的vector，<code>Vector</code>（§3.5.2，第4章）就是这样的例子。
容器接口的一致性让我们能够定义独立于特定容器类型的算法。可惜，有一利就有一弊。
比方说，对<code>vector</code>取下标和遍历开销小且易操作。
但是<code>vector</code>在插入或移除元素的时候，要对元素进行移动；<code>list</code>的特性则刚好相反。
请注意，对于小元素构成的较短序列，<code>vector</code>通常比<code>list</code>高效
（就连<code>insert()</code>和<code>erase()</code>也是如此）。
我推荐标准库的<code>vector</code>作为元素序列的默认类型：
如果你选择其它容器，就需要找到足够的理由。</p>
<p>考虑一下单链表，<code>forward_list</code>，一种专为空序列而优化的容器（§11.3）。
一个空的<code>forward_list</code>仅占据一个机器字的空间，而空<code>vector</code>要占三个。
空序列或者仅存放一或两个元素的序列，出乎意料地常见且有用。</p>
<p>在容器内直接构造元素（emplace）的操作，比如<code>emplace_back()</code>，
为一个元素的构造函数接收参数，并在容器中新分配的空间上构造出这个对象，
而不是把对象复制进入容器。
比如，对于<code>vector&lt;pair&lt;int,string&gt;&gt;</code>可以这么写<sup><a href="#fn_2" id="reffn_2">2</a></sup>：</p>
<pre><code class="lang-cpp">v.<span class="hljs-built_in">push_back</span>({<span class="hljs-number">1</span>,<span class="hljs-string">&quot;copy or move&quot;</span>});    <span class="hljs-comment">// 构造一个 pair 并移进 v</span>
v.<span class="hljs-built_in">emplace_back</span>(<span class="hljs-number">1</span>,<span class="hljs-string">&quot;build in place&quot;</span>); <span class="hljs-comment">// 在 v 里构造一个 pair</span>
</code></pre>
<p><a class="en-page-number" id="148"></a></p>
<h2 id="11.7">11.7 忠告 </h2>
<ul>
<li>[1] 一个 STL 容器定义一个序列；§11.2。</li>
<li>[2] STL 容器是资源执柄；§11.2，§11.3，§11.4，§11.5。</li>
<li>[3] 把<code>vector</code>作为你的默认容器；§11.2，§11.6；[CG: SL.con.2]。</li>
<li>[4] 为容器的简单遍历使用 区间-<code>for</code>
  或者迭代器的 begin/end 对；§11.2，§11.3。</li>
<li>[5] 使用<code>reserve()</code>以避免指向元素的指针和迭代器失效；§11.2。</li>
<li>[6] 未经测试的情况下，别对<code>reserve()</code>的性能优势抱有期待；§11.2。</li>
<li>[7] 在容器上<code>push_back()</code>或<code>resize()</code>，而不是在数组上<code>realloc()</code>；§11.2。</li>
<li>[8] 别用迭代器访问resize过的<code>vector</code>；§11.2。</li>
<li>[9] 别期待<code>[]</code>会进行越界检查；§11.2。</li>
<li>[10] 需要确保进行越界检查的情况下用<code>at()</code>；§11.2，[CG: SL.con.3]。</li>
<li>[11] 用 区间-<code>for</code> 和标准库算法可以零成本避免越界访问错误；§11.2.2。</li>
<li>[12] 元素进入容器的方式是复制；§11.2.1。</li>
<li>[13] 为保留元素的多态行为，请存储指针；§11.2.1。</li>
<li>[14] <code>vector</code>的插入操作，例如<code>insert()</code>和<code>push_back()</code>，
  效率通常意外的好；§11.3。</li>
<li>[15] 为通常置空的序列使用<code>forward_list</code>；§11.6。</li>
<li>[16] 涉及性能的时候，别主观臆断，先测试；§11.2。</li>
<li>[17] <code>map</code>通常是以红黑树的方式实现的；§11.4.</li>
<li>[18] <code>unordered_map</code>是个哈希表；§11.5.</li>
<li>[19] 以引用的方式传递容器，作为返回值的时候以值的方式返回；§11.2。</li>
<li>[20] 对于容器，用<code>()</code>-初始化 语法指定size，
  <code>{}</code>-初始化 语法指定元素列表；§4.2.3，§11.2。</li>
<li>[21] 优先使用紧凑连续的数据结构；§11.3。</li>
<li>[22] <code>list</code>的遍历操作相对高昂；§11.3。</li>
<li>[23] 如果需要在大规模数据中迅速查找，使用 unordered 容器；§11.5。</li>
<li>[24] 如果需要按顺序遍历元素，请使用有序的关联容器（即<code>map</code>和<code>set</code>）；§11.4。</li>
<li>[25] 为不需要常规顺序（即，不存在合理的<code>&lt;</code>）
  的元素类型使用unordered 容器；§11.4。</li>
<li>[26] 做试验以确保哈希函数是否可接受；§11.5。</li>
<li>[27] 用异或操作（<code>^</code>）将元素的标准哈希结果组合起来的哈希函数通常不错；§11.5。</li>
<li>[28] 去了解标准库容器并优先使用它们，
  而不要使用私下里手工打造的数据结构；§11.6。</li>
</ul>
<blockquote id="fn_1">
<sup>1</sup>. 这句话的原文出自“The Letters of Lord Nelson to Lady Hamilton, Vol II.”书中的“LETTER LX.”，该书可在网址 <a href="https://www.gutenberg.org/ebooks/15437" target="_blank">https://www.gutenberg.org/ebooks/15437</a> 查阅，未发现中文译本。 —— 译者注<a href="#reffn_1" title="Jump back to footnote [1] in the text."> ↩</a>
</blockquote>
<blockquote id="fn_2">
<sup>2</sup>. 原书第一行代码是<code>v.push_back(pair{1,&quot;copy or move&quot;)); // make a pair and move it into v</code>，无法通过编译，我改了一下。 —— 译者注<a href="#reffn_2" title="Jump back to footnote [2] in the text."> ↩</a>
</blockquote>

<script>console.log(window.location.pathname)</script>
<div id="disqus_thread"></div>
<script>

/**
*  RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS.
*  LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/
/*
var disqus_config = function () {
this.page.url = window.location.href;
this.page.identifier = window.location.pathname;
};
*/
(function() { // DON'T EDIT BELOW THIS LINE
var d = document, s = d.createElement('script');
s.src = 'https://a-tour-of-cpp-2nd-cn.disqus.com/embed.js';
s.setAttribute('data-timestamp', +new Date());
(d.head || d.body).appendChild(s);
})();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript" target="_blank">comments powered by Disqus.</a></noscript>
                                
    

                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="ch10.html" class="navigation navigation-prev " aria-label="Previous page: 10 输入输出">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="ch12.html" class="navigation navigation-next " aria-label="Next page: 12 算法">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"ch":11,"title":"11 容器","level":"1.13","depth":1,"next":{"title":"12 算法","level":"1.14","depth":1,"path":"ch12.md","ref":"ch12.md","articles":[]},"previous":{"title":"10 输入输出","level":"1.12","depth":1,"path":"ch10.md","ref":"ch10.md","articles":[]},"dir":"ltr"},"config":{"plugins":["@dogatana/page-toc-button","@dogatana/back-to-top-button","copy-code-button","forkmegithub","disqus-legacy"],"root":"./src","styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"pluginsConfig":{"@dogatana/back-to-top-button":{},"styles":{"website":"styles/website.css"},"search":{},"@dogatana/page-toc-button":{},"lunr":{"maxIndexSize":1000000,"ignoreSpecialCharacters":false},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"disqus-legacy":{"shortname":"a-tour-of-cpp-2nd-cn"},"copy-code-button":{},"forkmegithub":{"color":"orange","url":"https://github.com/windsting/a-tour-of-cpp-2nd-cn"},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false}},"theme":"default","author":"Windsting","pdf":{"pageNumbers":true,"fontSize":14,"fontFamily":"Arial","paperSize":"a5","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56},"embedFonts":false},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"C++导览 第二版 简体中文版","language":"zh-hans","links":{"sidebar":{"Github Link":"https://github.com/windsting/a-tour-of-cpp-2nd-cn"}},"gitbook":"*","description":"A Tour of C++ (第二版) 非官方中译本"},"file":{"path":"ch11.md","mtime":"2023-03-02T08:09:29.728Z","type":"markdown"},"gitbook":{"version":"5.1.1","time":"2023-10-27T09:54:29.738Z"},"basePath":".","book":{"language":""}});
        });
    </script>
</div>

        
    <noscript>
        <style>
            .honkit-cloak {
                display: block !important;
            }
        </style>
    </noscript>
    <script>
        // Restore sidebar state as critical path for prevent layout shift
        function __init__getSidebarState(defaultValue){
            var baseKey = "";
            var key = baseKey + ":sidebar";
            try {
                var value = localStorage[key];
                if (value === undefined) {
                    return defaultValue;
                }
                var parsed = JSON.parse(value);
                return parsed == null ? defaultValue : parsed;
            } catch (e) {
                return defaultValue;
            }
        }
        function __init__restoreLastSidebarState() {
            var isMobile = window.matchMedia("(max-width: 600px)").matches;
            if (isMobile) {
                // Init last state if not mobile
                return;
            }
            var sidebarState = __init__getSidebarState(true);
            var book = document.querySelector(".book");
            // Show sidebar if it enabled
            if (sidebarState && book) {
                book.classList.add("without-animation", "with-summary");
            }
        }

        try {
            __init__restoreLastSidebarState();
        } finally {
            var book = document.querySelector(".book");
            book.classList.remove("honkit-cloak");
        }
    </script>
    <script src="gitbook/gitbook.js"></script>
    <script src="gitbook/theme.js"></script>
    
        
        <script src="gitbook/@dogatana/honkit-plugin-page-toc-button/plugin.js"></script>
        
    
        
        <script src="gitbook/@dogatana/honkit-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-copy-code-button/toggle.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-forkmegithub/plugin.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-search/search-engine.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-search/search.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-lunr/lunr.min.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-lunr/search-lunr.js"></script>
        
    
        
        <script src="gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

